package BSQX_Bit;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class BSQX_4_14 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        BSQX_4_14 s=new BSQX_4_14();
        int n = s1.length();
        int m = s2.length();
        // 有一个字符串为空串
        if (n * m == 0) {
            System.out.println(n+m);
        }
        // DP 数组
        int[][] D = new int[n + 1][m + 1];
        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }
        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (s1.charAt(i - 1) != s2.charAt(j - 1)) {
                    left_down += 1;
                }
                D[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        System.out.println(D[n][m]);
    }



    public int minDistance2(String s1, String s2) {
        /*动规题- 三步奏
        * 1:划分子问题
        * 2:找递推关系
        * 3:确定计算顺序*/
        int count=0;
        if (s1.length() == s2.length()){
            for (int i = 0; i < s1.length(); i++) {
                //长度一致,就需要找不同的字符
               if (s1.charAt(i) != s2.charAt(i)){
                   count++;
               }
            }
        }else {
            count+=1;
            if (s1.length() > s2.length()){
                s2=s2+s1.substring(s2.length(),s1.length());
                for (int i = 0; i < s1.length(); i++) {
                    //长度一致,就需要找不同的字符
                    if (s1.charAt(i) != s2.charAt(i)){
                        count++;
                    }
                }
            }else {
                s1=s1+s2.substring(s1.length(),s2.length());
                for (int i = 0; i < s1.length(); i++) {
                    //长度一致,就需要找不同的字符
                    if (s1.charAt(i) != s2.charAt(i)){
                        count++;
                    }
                }
            }
        }
        return count;
    }
    public int getValue(int[] gifts, int n) {
        Arrays.sort(gifts);
        int count=0;
        for (int i = 0; i < n; i++) {
            if (gifts[i] ==  gifts[n/2]){
                count++;
                if (count > n/2){
                    return gifts[n/2];
                }
            }
        }
        return 0;
    }
}
